#include "stdio.h"
#include <string.h>
int main(int argc, char *argv[]) {
  short p0 = 0, p1 = 1, p2 = 2, p3 = 3, p4 = 4, p5 = 5, p6 = 6;
  char *p = argv[1];
  short *state = &p0;
  short *next_state_0[] = {NULL, &p2, &p2, &p4, &p2, &p2},
        *next_state_1[] = {&p1, &p3, &p3, &p3, &p5, &p3};
  if (argc != 2) {
    fprintf(stderr, "usage: %s <string>\n", argv[0]);
    return 1;
  }
  if(strcmp(argv[1],  "help")==0){
    printf("usage: %s <string>\n", argv[0]);
    printf("This is a DFA that accepts strings that contain 1(0|1)*101\n");
    printf("return 0 if the string is accepted, 1 if not\n");
    printf("2 if the string contains invalid characters\n");
    return 0;
  }
  for (; *p && (state != &p5); p++) {
    printf("%2d", state ? *state : -1);
    if (*p == '0') {
      state = (next_state_0[*state]);
    } else if (*p == '1') {
      state = (next_state_1[*state]);
    } else {
      fprintf(stderr, "invalid character: at %ld: %c\n",p-argv[1], *p);
      return 2;
    }
    printf("=>%2d\n", state ? *state : -1);
    if (state == NULL) {
      fprintf(stderr,"cannot recognize this string\n");
      return 1;
    }
  }
  if (state != &p5) {
    printf("no match\n");
    return 1;
  }
  printf("match\n");
  return 0;
}